#include <iostream>
#include <ctime>
#include <string>
#include <vector>

using namespace std;

struct Suf{
	int L, p;
	Suf(int L, int p): L(L), p(p) {}
};


void Push(vector<Suf> & v, Suf suf)
{
	if(suf.L <= v.back().L) return;
	if(suf.p == v.back().p && v.back().L >= 2 * v.back().p)
	{
		v.back().L = suf.L;
		return;
	}
	v.push_back(suf); //???
}
vector<vector<char> > M;
vector< vector<Suf> > allSuff;


void init(string s)
{
	vector<Suf> suf;
	int n = s.length() - 1;
	suf.push_back( Suf(1, 1) );	
	allSuff.push_back(vector<Suf>());
	allSuff.push_back(suf);
	for(int i = 2; i <= n; i++)
	{
		vector<Suf> newSuf;
		newSuf.push_back( Suf(1, 1) );
		if(s[i] == s[i - 1])
			newSuf.push_back( Suf(2, 1) );
		for(int j = 0; j < suf.size(); j++)
		{
			int L = suf[j].L + 2, p = suf[j].p;
			if(s[i] != s[i - L + 1 + p]) p = L - newSuf.back().L;
			if(s[i] != s[i - L + 1]) L -= p;
			Push(newSuf, Suf(L, p));
		}
		suf = newSuf;
		allSuff.push_back(suf);
	}
}


vector<char> doIter(string s, const vector<char> & m)
{
	int n = s.length() - 1;
	vector<char> res, z(n + 1);
	res.reserve(n + 1);
	res.push_back(false);
	res.push_back(m[0]);
	for(int i = 2; i <= n; i++)
	{
		vector<Suf> & suf = allSuff[i];
		bool curPref = false;
		for(int j = 0; j < suf.size(); j++)
		{
			int L = suf[j].L, p = suf[j].p;
			if(L < 3 * p) z[i - L] = m[i - L];
			z[i - L] |= m[i - p - L % p];
			curPref |= z[i - L];
		}
		res.push_back(curPref);
	}
	return res;
}


bool inThis(Suf suf, int L_)
{
	return L_ <= suf.L && (suf.L - L_) % suf.p == 0;
}


bool isPal(int start, int finish)
{
	for(int i = 0; i < allSuff[finish].size(); i++)
	{
		if(inThis(allSuff[finish][i], finish - start + 1) )
		{
			return true;
		}
	}
	return false;
}


bool isPal(string s)
{
	string p = s;
	reverse(p.begin(), p.end() );
	return s == p;
}


bool good(string s, vector<string> split)
{
	string res;
	for(int i = 0; i < split.size(); i++)
	{
		if(!isPal(split[i]) ) return false;
		res += split[i];
	}
	return res == s;
}


void getAns(int k, int n, string s)
{
	int K = k;
	string S = s.substr(1, n);
	//cout << S << " " << K;
	if(M[k][n])
	{
		vector<string> res;
		for(; k > 0; k--)
		{
			for(int i = 1; i < n; i++)
			{
				if(!M[k - 1][i]) continue;
				if(!isPal(i + 1, n)) continue;
				res.push_back(s.substr(i + 1, n - i) );
				n = i;
				break;
			}
		}
		res.push_back(s.substr(1, n) );
		reverse(res.begin(), res.end() );
		if(!good(S, res) || res.size() != K)
		{
			throw;
		}
		//cout << " = ";
		//for(int i = 0; i < res.size(); i++)
		//{
		//	cout << res[i];
		//	if(i + 1 != res.size() )
		//		cout << " + ";
		//}
		//cout << endl;
	}
	else
	{
		//cout << "!" << endl;
	}
}


void run(string s, int k)
{
	M.clear();
	allSuff.clear();
	int n = s.size();
//	printf("%s\n", s.c_str());
	s = "#" + s;
	init(s);
	vector<char> m(n + 1, false);
	m[0] = true;
	M.resize(k + 1);
	M[0] = m;
	for(int i = 0; i < k; i++)
	{
		M[i + 1] = m = doIter(s, m);
		for(int j = 1; j <= n; j++)
		{
			getAns(i + 1, j, s);
		}
	}
}


string getRand()
{
	int n = 10;
	string res;
	for(int i = 0; i < n; i++)
	{
		res += abs ( rand() ) % 3 + 'a';	
	}
	return res;
}


void main()
{
	srand(time(0) );
	for(int i = 0; ; i++)
	{
		string s = getRand();
		int k = s.length() + 5;
		run(s, k);
		if(i % 100 == 0)
			printf("%d\n", i);
	}
}


